package 二叉树高频题目_下_不含树型dp;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 修剪搜索二叉树
// 测试链接 : https://leetcode.cn/problems/trim-a-binary-search-tree/
public class Code06_TrimBinarySearchTree {

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }

    // 范围 [low, high]
    public TreeNode trimBST(TreeNode cur, int low, int high) {
        if(cur == null){
            return null;
        }
        // 如果当前节点的值小于low那么说明这个节点的整个左树都应该被砍掉
        if(cur.val < low){
            return trimBST(cur.right, low, high);
        }
        // 如果当前节点的值大于high那么说明这个节点的整个右树都应该被砍掉
        if(cur.val > high){
            return trimBST(cur.left, low, high);
        }
        // 重构搜索二叉树的左右子树
        cur.left = trimBST(cur.left, low, high);
        cur.right = trimBST(cur.right, low, high);
        return cur;
    }
}
